\section{Density-based objective}
\label{sec:theory1}

\begin{claim}
{\it Density-sTF} and {\it Density-mTF} problems are NP-complete.
\end{claim}
\begin{proof}
We prove the $claim$ by a reduction from the {\it Densest at least $k$ subgraph (DalkS)} problem defined in ~\cite{KS}. An instance of {\it DalkS} consists of a graph $G({\cal X}, E)$, and a constant $k$ and the solution is a maximum density subgraph with at least $k$ nodes. We transform it into an instance of {\it Density-sTF} problem by defining a skill $a$ for every node $v \in V$ in which case a solution would be a maximum density subgraph with at least $k$ nodes that have skill $a$. And since skill $a$ is defined for every node in $G$, it is easy to see that ${\cal X'} \subseteq {\cal X} $ is the solution to the problem {\it Density-sTF}  iff it is a solution to the problem {\it DalkS}. The problem {\it Density-sTF} is a special case of {\it Density-mTF} which implies that {\it Density-mTF} is NP-hard. 
\end{proof}

\subsection{3-approximation algorithm for {\it Density-sTF}}
\label{subsec:density-sTF}
In this section, we present the algorithm {\it s-DensestAlk} for the {\it Density-sTF} problem and prove that it achieves 3-approximation factor. 

{\it Intuition}: To begin with, the algorithm $s-DensestAlk$ accepts the graph and the skill requirements as an input. It then finds the densest subgraph and removes it from the input graph and adds it to the solution subgraph (which is initially empty). It then checks if the solution subgraph satisfies the skill  requirements. Until the solution subgraph constructed so far, meets the skill requirements the algorithm continues to iterate this process of finding the densest subgraph of the remaining input graph and adding it to the solution subgraph. Since, in each iteration, algorithm adds the densest subgraph, it is ensured that the solution subgraph has sufficiently high density. Note that although this algorithm guarantees the $3$-approximation ratio in terms of density, the solution subgraph may be larger than the optimal graph. We overcome this drawback by applying various simple polynomial time heuristic algorithms which are described in the section ~\ref{subsec:heuristic}.

{\it Details}: The algorithm {\it s-DensestAlk(G, {\cal T})}  accepts input parameters, namely, graph $G$ and task ${\cal T} = \lbrace <a_1, k_1> \rbrace$ where at least $k_1$ individuals/nodes of skill $a_1$ are required to perform the task ${\cal T}$. As explained intuituvely, the algorithm then proceeds through multiple iterations. In each iteration, $i$, it finds the maximum density subgraph, $H_{i+1}$ of $G_i$, removes it from $G_i$ using the routine $shrink(G_i, H_{i+1})$ and constructs a new solution subgraph $D_{i+1}$using the routine $union(D_i, H_{i+1})$. The routine $shrink(G, H)$ removes $H$ from $G$ such that for each $v \in (G - H)$, if $v$ has $l$ edges to the vertices in $H$, then it adds $l$ self-loops to $v$ with the corresponding edge-weights. Inside the routine $union(D, H)$, then for each loop, we look at its corresponding edge, say $e(u, v)$, in the original input graph, $G$, and if $u \in D, v\in H$ (or vice-versa), we replace the loop by an edge $e(u, v)$. Then once the terminating condition is satisfied, the algorithm then examines each of the intermittent solution subgraphs, $D_i$, constructed in previous iterations and adds sufficient number of skilled nodes so that each $D_i$ satisfies the skill requirement. The algorithm then picks up the one with the highest density as the final solution subgraph. 

Our algorithm is very similar to the $DensestAtleastK$ algorithm in ~\cite{KS} that calculates the maximum density subgraph containing at least $k$ vertices without any skill constraints imposed. The naive extention would be to just add $k$ skilled nodes to the solution returned by algorithm $DensestAtleastK$ in ~\cite{KS}. And since their algorithm guarantees an approximation factor of $2$ for density, this naive extension would guarantee an approximation factor of $4$ (proof ommitted for brevity). But, since the addional $k$ nodes are picked at random the solution may suffer from many disconnected components making it practically infeasible to be of any use. Therefore, we propose the  algorithm {\it s-DensestAlk} that differs mainly in the loop-termination condition imposed. This condition ensures that the resulting solution satifies the condition of at least $k$ nodes with the desired skills, improves the approximation ratio to $3$ from $4$ and has good connectivity property.

Although proof for $4$-approximation is simpler, it turns out that proving a 3-approximation to {\it Density-sTF} is significantly harder. While the algorithm is simple, the analysis is fairly detailed. The key idea is to consider various cases about the returned subgraph and carefully examine the density of each component. The analysis is similar to~\cite{KS} at the high level. However, due to the skillset constraints, several sub-cases needs to be considered.

\begin{algorithm}{s-DensestAlk($G, {\cal T}$)}
\begin{algorithmic}[1]
\STATE $D_0  \leftarrow \phi, \ G_0 \leftarrow G, \ i \leftarrow 0$
\WHILE{ $|D_i \cap S(a_1)| < k_1$ where ${\cal T} = \lbrace <a_1, k_1> \rbrace$}
\STATE $H_{i + 1} \leftarrow$ maximum-density-subgraph$(G_i)$
\STATE $D_{i + 1} \leftarrow union(D_i, H_{i + 1})$
\STATE $G_{i + 1} \leftarrow shrink(G_i,  H_{i + 1})$
\STATE $i \leftarrow i + 1$
\ENDWHILE
\FOR {$each \ D_i$}
\STATE $n_{a1} =$ number of nodes of skill $a_1$ in $D_i$
\STATE Add $max(k_1 - n_{a1}, 0)$ nodes of skill $a_1$ to $D_i$ to form $D'_i$
\ENDFOR
\STATE Return $D'_i$ which has the maximum density
\end{algorithmic}
\end{algorithm}

\begin{theorem}
The algorithm {\it s-DensestAlk} achieves an approximation factor of 3 for the {\it Density-sTF} problem.
\end{theorem}
\begin{proof}
\setcounter{equation}{0}
If the number of iterations is 1, then $H_1$ is the maximum density subgraph that contains at least $k$ nodes of skill $a$. Therefore, $H^* = H_1$ and the algorithm returns it. Otherwise, say the algorithm iterates for $l \ge 2$ rounds. There can be two cases:

\noindent {\bf Case 1:} There exists a $l' < l$ such that \\
$W(D_{l' - 1} \cap H^*) \le \frac{W(H^*)}{2}$  and  $W(D_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$.

\noindent {\bf Case 2:} There exists no such $l' < l$.

Before analyzing the two cases in detail, note that by construction
%, owing to the way the algorithm {\it s-DensestAlk} constructs, $D_i$ and $H_i$\\
$density(H_i) \le density(D_i) \le density(D_{i - 1})$. We now consider case 2 first and later case $1$.

\noindent {\bf Proof for Case 2.} 

Since the algorithm terminates after $l$ iterations, $D_l$ contains at least $k$ nodes of skill $a$. Further, we know that for each $j \le l - 1, W(D_j \cap  H^*)  \le \frac{W(H^*)}{2}$ \\ 
$\Rightarrow W(G_j \cap  H^*)  \ge \frac{W(H^*)}{2}$ \\ 
$\Rightarrow \frac{W(G_j \cap H^*)}{|V(G_j \cap H^*)|} \ge \frac{W(H^*)}{2 |V(H^*)|}$ \\ 
$\Rightarrow G_j$ contains a subgraph of density $\ge \frac{d^*}{2}$ \\ 
$\Rightarrow density(H_l) \ge \frac{d^*}{2}$ \\ 
$\Rightarrow density(D_l) \ge \frac{d^*}{2}$
%(The last step follows because by construction $D_l = H_1 \cup H_2 \cdot \cdot \cdot \cup H_l$) 

Thus, $D_l$ has density $\ge \frac{d^*}{2}$ and contains at least $k$ nodes of skill $a$. Therefore, the algorithm indeed returns a subgraph of density at least $\ge \frac{d^*}{2}$.

\noindent{\bf Proof for Case 1}

\noindent $W(D_{l' - 1} \cap H^*) \le \frac{W(H^*)}{2}$  and  $W(D_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$\\
$\Rightarrow W(G_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$ where $G_{l'} = shrink(G, D_{l' -1})$ \\ 
$\Rightarrow \frac{W(G_{l'} \cap H^*)}{|V(G_{l'} \cap H^*)|} \ge \frac{W(H^*)}{2 |V(H^*)|} = \frac{d^*}{2}$ \\ 
$\Rightarrow G_{l'}$ has a subgraph of density $\ge \frac{d^*}{2}$ \\ 
$\Rightarrow density(H_{l'}) \ge \frac{d^*}{2}$  ($H_{l'}  \mbox { is densest subgraph of } G$) \\ 
$\Rightarrow density(D_{l'}) \ge \frac{d^*}{2}$

Now, let us divide {\bf Case 1} into following $4$ parts 
\begin{enumerate}[(a)]
\item $|V(D_{l'})| \le  \frac{k}{2}$ \\
$density(D_{l'}) = \frac{W(D_{l'})}{|V(D_{l'})|} \ge \frac{W(H^*)}{2}\frac{2}{k} \ge \frac{E(H^*)}{ |V(H^*)|} \ge d^*$ 

According to step $10$, algorithm adds at most $k$ vertices to $D_{l'}$. Therefore, the resulting subgraph, $D'_{l'}$ has density $d \ge \frac{d^*}{3}$.

\item $|V(D_{l'})| \ge  2k $

According to step $10$, algorithm adds at most $k$ vertices to $D_{l'}$. Further, we know that $density(D_{l'}) \ge \frac{d^*}{2}$ therefore, the resulting subgraph, $D'_{l'}$ has density 

\noindent $d = \frac{W(D_{l'})}{|V(D_{l'})| + k} \ge \frac{W(D_{l'})}{\frac{3}{2} |V(D_{l'})|}  \ge  \frac{d^*}{3}$

\item $\frac{k}{2} < |V(D_{l'})| <  2k$ and $ |V(D_{l'}) \cap V(H^*)| \ge \frac{|V(H^*)|}{2}$

According to step $10$, algorithm adds at most $\frac{|V(H^*)|}{2}$ nodes to $D_{l'}$ to form $D'_{l'}$ with density, say $d$.

\begin{enumerate}[i]
\item $|V(D_{l'})| \ge |V(H^*)|$ \\
$d = \frac{W(D_{l'})}{|V(D_{l'})| + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(D_{l'})| + \frac{|V(D_{l'})|}{2}} =   \frac{\frac{W(H^*)}{2}}{\frac{3}{2}|V(H^*)|} \ge \frac{d^*}{3}$ 

\item $|V(D_{l'})| \le |V(H^*)|$ \\
%$d = \frac{W(D_{l'})}{|V(D_{l'}|) + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(H^*)| + \frac{|V(H^*)|}{2}} \ge  \frac{\frac{W(H^*)}{2}}{\frac{3}{2}|V(H^*)|} \ge \frac{d^*}{3}$
$d = \frac{W(D_{l'})}{|V(D_{l'}|) + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(H^*)| + \frac{|V(H^*)|}{2}} \ge \frac{d^*}{3}$
\end{enumerate} 

\item $\frac{k}{2} < |V(D_{l'})| <  2k$ and $|V(D_{l'}) \cap V(H^*)| < \frac{|V(H^*)|}{2}$

If $d_{l'} = density(D_{l'}) \ge d^*$, then adding at most $k$ vertices gives a subgraph $D'_{l'}$ with density, say $d$ such that

\noindent $d = \frac{W(D_{l'})}{ |V(D_{l'})| + k} \ge \frac{W(D_{l'})}{|V(D_{l'})| + 2 |V(D_{l'})|}  \ge \frac{W(D_{l'})}{3 |V(D_{l'})|} \ge \frac{d^*}{3}$

Therefore, $D'_{l'}$ is a subgraph that contains at least $k$ nodes of skill $a$ and has density $d \ge \frac{d^*}{3}$. We are done here.

Now, assume that $d_{l'} < d^*$.

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.25, bb = 30 300 500 700]{3_approx_dia_1.eps}
\caption{$D_{l'} = D_{i1} \cup D_{i2} \cup X$}\label{fig:3approx}
\end{center}
\end{figure}
In the rest of the proof, we divide $D_{l'}$ into subgraphs as explained below and shown in Figure~\ref{fig:3approx}. 

$\mbox{Let } G' = D_{l'} \cap H^* $ \\
$\Rightarrow |V(G')| = |V(D_{l'} \cap H^*)| < \frac{|V(H^*)|}{2} $ \\ 
$\mbox {and } W(G') = W(D_{l'} \cap H^*) \ge  \frac{W(H^*)}{2} $ \\
$\Rightarrow density(G') \ge \frac{\frac{W(H^*)}{2}}{\frac{|V(H^*)|}{2}} \ge d^* $ \\
$\Rightarrow W(G') \ge \frac{W(H^*)}{2} \ge \frac {d^*|V(H^*)|}{2} $ \\
Let, $density(H_i)  > d^*$ and $density(H_{i+1}) < d^*$\\  
$\Rightarrow density(D_i)  = d_i > d^*$ 

Let, $n_i = |V(D_i)| $

If $n_i \ge \frac{|V(H^*)|}{2}$ then, add at most $k$ vertices to $D_i$ to get a subgraph $D'_i$ with $density(D'_i) = d$, such that  \\
$d = \frac{W(D_i)}{|V(D_i)| + k} \ge \frac{W(D_i)}{|V(D_i)| + |V(H^*)|} \ge \frac{W(D_i)}{3 |V(D_i)|} \ge \frac{d^*}{3}$ \\ 
Thus, $D'_i$ is a subgraph containing at least $k$ nodes of skill $a$ and density $d \ge  \frac{d^*}{3}$ and we are done here.

Now, assume that $n_i < \frac{|V(H^*)|}{2}$\\ 
We know that $G'$ is a subgraph of $D_{l'}$ with $density(G') >  d^*$, however, $density(D_{l'}) < d^*$. And we also know that $D_i$ is a subgraph of $D_{l'}$ such that $density(D_i) > d^*$ and $density(D_{i+1}) < d^*$.  Therefore, there exists a sub-graph of $G'$ that is contained in $D_i$.

Let us define \\
$D_{i1} = D_i \cap G'$  and $D_{i2} = shrink(D_i, D_{i1})$ and \\  
$G'' = shrink(G', D_{i1})$\\
$\Rightarrow G' = D_{i1} \cup G''$ \\

As proved earlier, $W(G')  \ge \frac{|V(H^*)| d^*}{2}$ \\  
$\Rightarrow W(D_{i1}) + W(G'') \ge  \frac{|V(H^*)| d^*}{2} $  \\ 
$\Rightarrow W(D_{i1}) \ge  \frac{|V(H^*)| d^*}{2} - W(G'') $

As defined earlier, $density(H_i) > d^*$ \\
$\Rightarrow$ for each $j \le i, density(H_j) > d^*$. \\ 
Further, $H_j = \mbox{ densest subgraph of } shrink(G, D_{j-1})$ \\
$\Rightarrow$ for each $v\in H_j$ or $v\in D_i$, $degree(v) > d^*$ \\
%$\Rightarrow$ for each $v \in D_i, degree(v) > d^*$ \\
$\Rightarrow density(D_{i2}) > \frac{d^*}{2}$

Now, let us define $X = shrink(D_{l'}, D_i)$; $\Rightarrow G'' \subseteq X$ \\
Further, $n_{x} = |V(X)|$, $n_{l'} = |V(D_{l'})|$, and $n'' = |V(G'')|$.

Since $H_{l'}$ is the maximum density subgraph of $shrink(G, D_{l'-1})$, for any $S \subseteq H_{l'},$ \\
$density(H_{l'})  \ge density(S)$ \\
$\Rightarrow density(H_j) \ge density(H_j \cap G'')$ (for all $j \le l'$)\\ 
Further, $X = H_{i+1} \cup H_{i + 2} \cup \cdot \cdot \cdot H_{l'}$ \\
$\Rightarrow density(X)  \ge density(G'')$ $\Rightarrow d_x \ge d''$.
%$\ge d_{x1}n_{x1} - d''n''
%\frac{d^*}{2}(n_{x1} - n'')$ \\ \\

%Now, before completing the analysis, recall 
%$V(G) = $ a vertex set of $G$ \\
%$D = $ a graph obtained by adding at most $k$ nodes of skill $a$ to $D_{l'}$ \\
%$n_{l'} = | V(D_{l'}) |$  \\  \\

We now complete the analysis. 

\noindent $d = density(D) = \frac{W(D_{l'})}{n_{l'} + k}$ \\
$\ge \frac{W(D_i) + E(X)}{n_{l'} + k}$ \\ 
$= \frac{W(D_{i1}) + W(D_{i2}) + W(X)}{n_{l'} + k}$ \\ 
$\ge \frac{\frac{d^* |V(H^*)|}{2} - W(G'') + \frac{d^*n_{i2}}{2} + d_xn_x}{n_{l'} + k}$ (Note : $d_{i2} \ge \frac{d^*}{2}$)\\ 
$\ge \frac{\frac{d^* |V(H^*)|}{2} - d''n'' +  \frac{d^*n_{i2}}{2} + d_xn_x}{n_{l'} + k}$ \\ 
%$\ge \frac{\frac{d^* |V(H^*)|}{2} + \frac{d^*n_{i2}}{2} + d_x(n_x - n'')}{n_{l'} + k}$  (Note : $d_x \ge d''$) \\ 
$\ge \frac{\frac{d^* |V(H^*)|}{2} + \frac{d^*n_{i2}}{2} + \frac{d^*}{2}(n_x - n'')}{n _{l'}+ k}$  (Since $d_x\ge\frac{d^*}{2}$, $d_x\ge d''$, $n_x\ge n''$)\\ 
%$= \frac{d^*}{2} \frac{|V(H^*)| + n_{i2} + n_{x} - n'' - n_{i1} + n_{i1}}{n_{l'} + k}$ \\ 
%$= \frac{d^*}{2} \frac{|V(H^*)| + n_{i1} + n_{i2} +n_{x} - (n'' + n_{i1})}{n_{l'} + k}$ \\ 
$= \frac{d^*}{2} \frac{|V(H^*)| + n_{i1} + n_{i2} +n_{x} - |V(G')|}{n_{l'} + k}$ (Using $G' = D_{i1} \cup G''$)\\ 
$\ge \frac{d^*}{2} \frac{|V(H^*)| + n_{l'} - \frac{|V(H^*)|}{2}}{n_{l'} + k}$ (Note: $|V(G')|  \le \frac{|V(H^*)|}{2}$) \\ 
%$= \frac{d^*}{4} \frac{2n_{l'} + |V(H^*)|}{n_{l'} + k}$ \\ 
%$\ge \frac{d^*}{4} \frac{2n_{l'} + k}{n_{l'} + k}$ \\ 
$\ge \frac{d^*}{4} \frac{2n_{l'} + k}{n_{l'} + k} \ge \frac{d^*}{3}$ (apply the inequality $\frac{k}{2} < n_{l'} < 2k$).
\end{enumerate}
\end{proof}

\subsection{3-approximation algorithm for {\it Density-mTF}}
In this section, we present the algorithm {\it m-DensestAlk} for the {\it Density-mTF} problem. This is an extension of the algorithm {\it s-DensestAlk} for the {\it Density-sTF} problem which attempts to find a densest subgraph containing at least $k$ nodes of only one skill, say $a_1$. The algorithm  $m-DensestAlk(G, {\cal T})$ accepts input parameters: graph $G$ and  task ${\cal T} = \lbrace <a_1, k_1>, <a_2, k_2>, \cdot \cdot \cdot, <a_m k_m>\rbrace$  which requires at least $k_i$ individuals of skill $a_i$ to perform the task $\cal T$. Each iteration within the algorithm {\it m-DensestAlk} is exaclty similar to the {\it s-DensestAlk} described earlier except that here the termination condition verifies that the solution subgraph contains atleast $k_i$ nodes with skill $a_i$ for $i \in \lbrace 1 \cdot \cdot m \rbrace$ and thus satisfying the {\it multiple} skill requirement instead of {\it single} skill requirement. The details of the algorithm are similar to that described for {\it s-DensestAlk} in the section ~\ref{subsec:density-sTF}.

\begin{algorithm}{m-DensestAlk($G, {\cal T}$)}
\begin{algorithmic}[1]
\STATE $D_0  \leftarrow \phi, \ G_0 \leftarrow G, \ i \leftarrow 0$
\WHILE{ $|D_i \cap S(a_j)| < k_j$ for any $<a_j, k_j> \in {\cal T}$}
\STATE $H_{i + 1} \leftarrow$ maximum-density-subgraph$(G_i)$
\STATE $D_{i + 1} \leftarrow union(D_i, H_{i + 1})$
\STATE $G_{i + 1} \leftarrow shrink(G_i,  H_{i + 1})$
\STATE $i \leftarrow i + 1$
\ENDWHILE
\FOR {$each \ D_i$}
\STATE $D'_i \leftarrow D_i$
\FOR {$each \ <a_j, k_j> \in {\cal T}$}
\STATE $n_{aj} =$ number of nodes of skill $a_j$ in $D_i$
\STATE Add $max(k_j - n_{aj}, 0)$ nodes of skill $a_j$ to $D'_i$
\ENDFOR
\ENDFOR
\STATE Return $D'_i$ which has the maximum density
\end{algorithmic}
\end{algorithm}

\begin{theorem}
The algorithm {\it m-DensestAlk} achieves an approximation factor of 3 for the {\it Density-mTF} problem.
\end{theorem}
\begin{proof}
Let $k = \sum_{j=1}^{m}{k_j}$ where $k_j$ indicates the number of individuals required of skill $<a_j, k_j> \in {\cal T} \ (1 \le j \le |{\cal T}|)$. Therefore, an optimal solution, $H^*$, has at least $k$ vertices. The proof for {\it m-DensestAlk} is analogous to the proof for {\it s-DensestAlk} with the only difference that instead of adding any $k$ nodes of skill $a$ to $D_i$s, we add $k_j$ nodes of skill $a_j \in {\cal T} \ (1 \le j \le |{\cal T}|)$.
\end{proof}

{\it Time Complexity.} In the algorithm {\it s-DensestAlk}, the while loop in line $2$ iterates at most $n = |V(G)|$ times. In each iteration, the densest subgraph is computed using the algorithm in Goldberg~\cite{G84} which runs in time $O(n^3 \log{n})$. So, the total time spent in constructing all $D_i$s (lines $2$-$7$) is $O(n^4 \log n)$. This dominates the time required to construct all $D'_i$s and to choose the densest of them (lines $8$-$12$). Similarly, 
%in {\it MultiiSkillDensestAtleastK}, the time required to construct all $D'_i$s and also to choose the one with maximum density (lines $8$-$15$)  is $O(n|{\cal T}|)$. Therefore, 
the running time of algorithm {\it m-DensestAlk} is also $O(n^4 \log n)$. In practice, however, both these algorithms are likely to run significantly faster; in particular, since the size of the returned subgraph is fairly small (let us say $O(k)$ and independent of $n$), the time complexity is more like $O(n^3k)$. 

{\it Comment.} $O(n^3)$ can still be inefficient for very large graphs but is manageable at the scale at which we run experiments. There is a linear time 3-approximation algorithm for the densest at least $k$ subgraph problem suggested in~\cite{KS,AC} but this would only translate to a $6$-approximation algorithm for {\it Density-sTF}. Similarly, directly using the $O(n^3)$-time $2$-approximation algorithm from~\cite{KS,AC} would also result in a weaker bound (i.e. $4$-approximation) for {\it Density-sTF} or {\it Density-mTF}. Therefore, the extra computation performed in considering several solutions by modifying subgraphs from each of the iterations (and then picking the best) is beneficial in obtaining the improved $3$-approximation. 

Note that the resulting solution may however be large compared to $k$, and may also be disconnected. Later in Section~\ref{sec:exp}, we present heuristic post-processing steps on this algorithm to ensure a connected and sufficiently small solution (without compromising on the constraint on skilled nodes). We also show that this does not affect the resulting density significantly.
